package com.azure.code.dfs;

import java.util.LinkedList;
import java.util.List;

/**
 * 单词拆分
 * 给定一个字符串 s 和一个字符串字典wordDict，在字符串s中增加空格来构建一个句子，
 * 。以任意顺序 返回所有这些可能的句子。
 *
 * 注意：词典中的同一个单词可能在分段中被重复使用多次。
 *
 * 输入:s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
 * 输出:["cats and dog","cat sand dog"]
 *
 * 输入:s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
 * 输出:["pine apple pen apple","pineapple pen apple","pine applepen apple"]
 * 解释: 注意你可以重复使用字典中的单词。
 *
 */
public class WordBreakII_140 {
    List<String> res = new LinkedList<>();
    // 记录回溯的路径
    LinkedList<String> track = new LinkedList<>();
    public List<String> wordBreak(String s, List<String> wordDict) {
        // 根据函数判断s[0..] 是否能够拼出
        backTrack(s,0,wordDict);
        return res;
    }
    private void backTrack(String s,int i, List<String> wordDict){
         if(i == s.length()){
             res.add(String.join(" ",track));
             return;
         }
         if(i>s.length()){
             return;
         }
        for (String word : wordDict) {
            int len = word.length();
            // 单词太长跳过
            if(i+len>s.length()){
                continue;
            }
            // 无法匹配，跳过
            String subStr = s.substring(i,i+len);
            if(!subStr.equals(word)){
                continue;
            }
            // s[i..] 前缀被word 匹配，做选择
            track.addLast(word);
            backTrack(s,i+len,wordDict);
            // 撤销选择
            track.removeLast();
        }
    }
}
